﻿using System;
using System.Linq;

namespace LeetCode
{
    public class Solution
    {
        //设置两个向量leftsum, rightsum,作为比较，初始时，leftsum =0, rightsum为 下标1到最后 的所有元素的和。如果二者相等，则返回下标0。否则开始遍历数组，对于每一个元素，leftsum+=nums[i-1], rightsum-=nums[i]， 之后判断二者是否相等。
        public int PivotIndex2(int[] nums)
        {

            int count = nums.Count();

            if (count == 0)
                return -1;

            int leftSum = 0, rightSum = 0;
            for (var i = 1; i < count; i++)
            {
                rightSum += nums[i];
            }
            if (leftSum == rightSum)
                return 0;

            for (int i = 1; i < count; i++)
            {
                rightSum -= nums[i];
                leftSum += nums[i - 1];
                if (rightSum == leftSum)
                    return i;
            }

            return -1;

        }
        //暴力法，遍历数组，观察数组中的哪一个元素可以作为中心索引。运行时间O(n^2).
        public int PivotIndex(int[] nums)
        {
            int count = nums.Count();
            for (var i = 0; i < count; i++)
            {
                int sum1 = 0;
                for (var j = 0; j < i; j++)
                {
                    sum1 += nums[j];
                }
                int sum2 = 0;
                var k = i + 1;
                if (k < count)
                {
                    for (; k < count; k++)
                    {
                        sum2 += nums[k];
                    }

                }
                if (sum1 == sum2)
                {
                    return i;
                }
            }
            return -1;

        }
    }
    class Program
    {

        static void Main(string[] args)
        {
            int result = new Solution().PivotIndex2(new int[] { -965, -674, 696, -505, 842, -385, -389, -459, -763, 132, -310, -789, 990, 373, 375, -707, 761, -23, 988, -598, 703, -902, -582, 690, -498, 435, -618, 124, -347, 966, -898, -275, 888, -611, 940, -292, -341, 878, -181, -87, -133, 527, -506, -734, 191, 69, 214, -270, -339, -710, 456, -733, -667, -23, 151, -121, -395, 245, 59, -458, -20, 40, 667, -211, -560, 544, 54, 531, 853, 470, 5, -840, -346, 919, -226, -340, 679, 492, 435, -531, 97, 612, -412, 149, 707, -865, -821, -726, -620, 289, 33, -811, 776, -933, 675, 26, -281, 247, 498, -954, 795, -202, -59, 879, 357, 340, -467, 520, -569, -965, -48, 5, 870, -485, 474, 165, -239, 263, 383, 578, -767, 204, 316, -197, -25, -645, -577, 157, 15, -44, 331, -119, -746, -990, -656, 959, 810, -59, -674, -672, 803, -384, 982, -561, 374, -541, 164, 857, 461, -335, 108, 877, -154, 133, 797, 99, -753, 25, 900, 330, 486, -631, 646, 370, -460, -499, -443, 750, 645, 833, 418, 85, 11, -458, -609, -625, -348, -662, 967, 143, -64, -439, 650, 396, -802, -774, 281, -960, 526, 652, 428, 220, -548, -304, 297, -652, -75, -262, -762, 990, 859, 239, 943, 87, -547, 239, 213, -651, 499, -681, -511, 199, -550, -897, 45, -749, -609, -558, -826, -625, 193, 901, -926, -175, 595, -427, 679, -420, -554, -343, 911, -292, -428, -394, 933, -338, -446, -146, -656, -837, 190, 420, -459, 184, -357, 712, -752, -852, 56, -743, 319, -955, -349, 738, -502, -1, -798, 815, -816, 533, 941, -724, -913, 919, -122, -731, 972, -11, -548, -573, -443, -836, 478, -214, 937, -279, -127, 502, 184, 487, -754, -993, 493, 590, 716, -292, -74, -470, 18, -144, -189, -78, -237, -930, -937, 965, 82, 118, 283, 511, 972, 405, 199, 135, 123, -524, 525, 286, -793, 674, -318, 165, -343, 309, -6, 952, -53, -253, -276, 187, 405, 157, -307, 93, -258, -980, 662, -97, 320, -714, -689, 917, 93, 45, -105, -744, -295, 495, -139, 420, 954, 342, -317, -432, -62, -323, 427, 777, -842, 143, -465, -149, 672, -485, 184, 660, 964, -954, -303, 594, 946, 276, 320, -495, 818, 680, -823, -271, 280, -443, 120, 489, 295, -450, -895, 190, 627, -606, 11, -280, -482, -103, -127, -130, -67, 320, -957, 565, 263, 633, 229, 371, -515, -58, -586, -432, 991, 153, 647, -442, -566, 128, 576, 390, 254, -937, 712, 989, -953, 728, 867, -666, -346, 530, 627, 556, -54, -58, -654, -577, -805, 934, -520, -382, -158, 597, 972, -251, 312, -146, 69, 727, -702, -532, -482, 498, 138, -947, 854, -961, -915, -23, 639, -970, 784, 945, -1, -998, -926, -182, 523, -918, -856, 202, 764, -81, -147, -434, -349, -686, -628, 47, -27, 326, -859, -167, 132, -469, -895, 390, 145, 115, -639, -163, -578, 186, 210, 920, 949, -595, -700, 335, 873, 433, -392, 520, -127, 495, 320, -353, 914, 114, 470, -964, 949, 621, -264, -176, -273, -483, 247, -829, -911, 776, -967, -133, -242, -571, 98, 779, -752, -510, -270, -899, -247, -932, 491, -290, -745, 716, 911, -64, 25, 37, 549, -669, 409, 473, -32, -613, 849, -402, -647, -313, 67, -910, -237, 231, -756, -925, 52, 800, 535, 983, 259, 354, -209, -386, 448, 535, 669, -49, -272, -264, 707, 379, 857, 650, 881, 781, -323, 867, 593, -378, -185, 462, -405, 981, 99, 132, 241, 551, -21, 984, 720, 814, 217, -727, -958, -809, 652, 116, -634, 485, 47, 297, -89, 186, 668, 60, 467, 155, -516, -994, 847, 708, -840, 923, -242, 660, 142, -166, -863, 672, 593, 869, 217, 127, 48, -355, -244, 880, 980, -655, -787, -842, 498, -77, -429, 858, 776, -991, -793, 210, -876, 593, 664, 345, -545, -619, -894, -350, 497, -5, -882, 181, -662, -542, -528, 137, -386, 897, 888, -436, -787, 22, 708, 773, -751, 78, 237, 341, -327, -471, 576, -310, -549, 789, -619, -885, -303, 448, 261, -958, 824, -697, -289, 390, 75, -314, 969, -16, -115, -458, -670, -868, 200, 578, -690, -894, -127, 587, 267, -200, 848, -104, -771, 908, 623, 433, 98, -997, 631, 879, -498, -283, 210, 689, -259, -35, 769, -626, -596, 527, 500, -940, -881, -216, 114, -336, 210, 652, 199, -298, -894, -419, 390, -199, 446, -753, 63, 893, 309, -14, -613, -615, -273, 216, -167, 445, -317, -201, 217, 457, 78, 761, 49, 385, -394, -548, 746, -78, 498, -795, 164, -292, -849, -37, -65, 514, -95, 789, -35, 346, 566, -451, 435, -881, 157, 713, 169, -889, 621, -604, -840, -950, -544, 850, -206, -840, -126, 57, 772, -394, 382, 330, 884, -413, 414, 364, 291, -628, -913, -470, 252, -259, 731, 385, 721, 859, -985, -99, 433, 668, -138, 96, -638, 576, 309, 356, 652, -354, 950, -596, -329, -359, -658, 832, -133, 298, -994, 188, -868, -488, -447, -461, 816, 796, 97, -280, -37, 838, -421, 333, 469, -686, 603, 345, 249, -967, 726, 422, -390, 340, -526, 18, 395, 537, -783, 109, -397, -137, 471, -175, -748, 541, -444, -258, 577, 178, -456, 883, 926, -86, -482, 571, -18, 681, 4, 614, 946, 738, 75, -768, 916, -994, 405, 722, -783, -828, -187, 706, 89, -580, -991, 822, -779, 145, -260, -85, -460, 725, -208, 174, 397, -341, -49, -510, 11, 804, -780, -477, 973, 985, -78, -287, -684, -29, 940, 732, 853, -674, -282, -704, -245, 171, 447, -304, 373, -727, -818, -936, -4, -579, -570, 678, -517, -601, 647, -449, -603, 369, -80, 494, -714, 721, 588, -880, -779, -811, -834, 393, -364, -707, -963, 352, 830, 97, 676, -297, -694, 812, -992, -324, 511, 595, 834, -309, -553, 580, -993, 69, -219, -628, 927, 184, -745, 905, 911, -915, 920, 933, 413, 433, 753, 826, 829, 279, 150, 765, 226, -486, -723, 415, -36, 737, -970, 567, 728, 545, 20, -286, -481, -671, 195, -430, -636, 185, -897, 8, 987, -593, 22, -390, -540, 878, 777, -574, 955, -904, -702, -514, -803, -659, -982, 582, -35, -410, 389, -76, -931, -503, 704, 575, -352, 391, -712, 849, 590, 996, -192, -6, 612, 713, 129, 897, 454, -858, -481, 903, 185, -546, -9, -574, -267, -121, 451, 339, -387, 142, 923, -840, 630, 837, 755, -526, 333, -686, -550, 206, 116, -70, 660, -799, -40, -728, -419, 358, -816, -302, -606, 874, 306, 604, -997, 156, -561, -883, 857, -640, 39, 686, 55, 734, -442, 204, 41, 58, -364, 49, 45, -550, -474, 308, 372, 547, 269, 654, -857, 177, 565, -664, -867, 474, 498, 609, 251, -801, -31, 197, -233, -713, -21, -17, 728, 901, -978, 157, -792, -439, 931, -417, 871, 392, 438, 903, -419, -662, 438, -377, -61, 87, -367, 775, -611, -784, 532, -183, 963, 135, 868, -255, -480, 447, 557, -944, 394, -778, 54, -204, -399, -877, -94, 545, -800, -177, -453, -161, -64, -906, 609, -589, 476, 702, 530, 829, -996, 959, -696, 160, -908, 397, -113, 229, 658, 860, 149, 209, -791, 583, 144, -1000, -772, -122, -45, 276, -167, 318, 74, -172, -384, -413, 891, -673, -929, -128, -3, 101, 123, -503, 509, -799, -385, 34, 162, 370, 711, -177, -838, 737, -305, -987, 87, -990, 843, -282, -374, 241, 57, 288, 775, 755, -331, 602, 599, 122, 845, 142, 437, 607, -240, -999, 799, 24, -675, -913, 553, 144, -162, -114, 157, 640, 247, 536, -374, 160, 301, 711, 892, 463, 900, -206, -843, 292, -579, -374, -555, 443, 406, -899, 825, -88, -837, 191, -608, -799, 427, 659, -501, 932, 917, 230, -109, 836, -282, 689, -849, 458, 46, -725, 582, 142, -898, 302, 166, 443, -507, 372, 552, 21, 633, 139, -649, 458, -177, 731, 153, 4, -920, 424, -526, -277, 632, 918, 763, 714, -62, 776, 472, 496, 364, 767, 882, 415, 344, -786, -987, -200, 509, -872, 510, -882, 648, -454, -624, -980, 15, -304, 686, -932, -98, 861, -656, -240, 370, -575, 492, 638, -828, -120, 475, -460, -644, -482, 668, -802, -363, -181, -539, 521, 216, -387, 960, -788, 512, -95, -516, 689, -47, 571, -239, -931, 312, -678, -894, 274, 819, -782, -260, 718, -401, 234, 824, 738, 234, 363, -237, 687, -544, 165, 336, 207, -681, -267, 488, -586, 640, 639, -905, 523, -424, 577, 212, -154, -138, 479, -843, -225, -47, 206, -4, -538, -196, -661, 166, 874, -51, 400, 89, 528, -646, 223, -374, -460, -637, 794, -960, 315, 488, -311, -728, 301, -382, -593, 896, 516, 748, -81, -243, 339, 52, 571, 11, 578, 686, 369, -663, 807, 291, -167, 396, 297, 645, 452, -733, -470, 392, 214, -725, -85, 117, -487, 900, -277, -548, 405, -789, 625, -131, -819, 885, -665, 156, -127, 838, -271, 281, 709, -428, 837, 852, -84, -114, -797, -865, -764, -15, 157, 449, 11, -152, 78, 27, -199, 142, 826, -420, -638, -64, -874, -705, 452, 860, -803, -673, -113, -397, -722, -975, -954, 983, 689, -733, 242, -196, -824, 729, 576, 63, 377, -127, -593, 644, 300, 594, -68, -12, -660, -523, 451, -308, 330, -484, -537, 275, 491, -173, 106, 252, 786, 397, -666, -550, -19, 281, 407, -352, 297, 264, 973, 968, -894, 856, -62, 22, 456, 969, -428, 267, 66, -64, -66, -756, 943, -113, 578, 484, 294, -303, 949, -565, 829, 647, 974, -445, -273, 691, -371, 102, -282, -672, -102, 532, 77, 900, 115, 862, 683, -700, -468, 732, 797, 207, 368, -997, 499, -346, 762, -819, 306, -823, -645, 617, 779, 949, 413, -90, 141, -893, -422, -429, 502, -474, -338, -857, 684, -311, 375, -500, -25, 768, -143, 148, -869, -553, -237, 274, 254, -421, 596, -463, 625, 386, -91, -945, 927, 927, -804, -199, 891, -938, -471, 22, -706, 580, -807, 607, -47, 248, 340, 905, 767, -837, 793, -244, 145, 572, -300, -69, 896, -517, -350, 221, -461, -110, -117, -71, 468, -443, 972, -595, -238, 326, -421, -70, -844, 843, -377, 600, -373, 695, 1, 186, -889, -685, -98, -200, 287, -507, 538, -639, -446, 538, -827, 994, 1000, 715, 227, 514, 882, 427, -128, 151, -355, 95, -989, -736, 815, 108, -986, 756, 841, 665, 820, 453, 374, -676, -436, 828, -522, -935, 274, 823, -822, -153, -609, -91, -275, -553, -891, -831, -475, -208, 490, -663, -871, -833, 41, 40, -812, 214, -978, -995, -418, 667, 564, 701, 204, 841, 581, 137, -869, -194, 968, 942, 73, -512, -240, 27, -91, 770, -840, 708, 442, 415, 115, 327, 134, 840, 695, -18, -783, 470, 542, 136, 163, -326, -222, -974, 665, 537, 16, -339, -835, 181, -58, -395, -184, -743, 391, -688, -490, -147, 510, -652, -466, -312, 937, 178, -21, -245, 818, 681, -616, -322, 302, -764, 593, -287, 7, 305, 868, 464, -109, 287, 116, -477, -569, 567, 118, 397, -935, 525, -568, 959, -251, -652, 717, 967, 429, 391, -962, 944, -112, 166, 945, -377, -535, -890, 189, -855, -931, -918, -397, -553, -255, 433, 667, -654, 7, -746, 121, 780, 376, -38, 112, -798, 823, -903, -616, 340, 670, -586, 935, -900, 4, -536, -85, -431, -853, -425, -748, -278, 384, 185, 759, 566, -524, -526, 304, 295, 218, -161, -42, 6, 150, 251, -119, 179, 1000, -913, -920, 338, 935, 183, 259, 483, 393, -674, 876, -609, 414, 528, 898, -938, 239, 849, -408, 270, 690, 51, 550, -698, -462, -454, 994, 38, -152, -786, -304, -879, -885, -436, -152, -408, -882, -477, 444, -211, -47, -814, -167, -235, 403, 558, 8, -362, 171, 446, -300, 498, 133, 167, 105, 376, 407, 595, -21, -259, -123, -114, -222, -848, -264, 317, 834, 87, -98, -386, 502, 962, 873, 597, -98, -905, -381, -598, 359, -555, 973, -121, -77, 204, 255, 258, 919, -706, -389, 34, -289, -959, -856, -14, 641, 2, -585, -87, -353, 513, 981, -581, -381, -888, -66, 267, -591, 274, -321, 939, 331, -998, 978, -900, -143, -400, -956, 336, 372, -166, 179, 698, -213, -353, 252, 626, -889, 836, 38, 412, -877, 409, -958, 623, 808, 348, 62, -533, -271, 353, -23, -436, -30, -57, -828, -297, 621, -655, 405, -519, -493, -441, -645, 364, 988, 144, -309, 461, -390, 759, -123, -483, -785, -821, 643, 33, -292, -607, 601, 503, -276, -723, 642, 261, -983, -203, 404, -684, -634, 697, 301, -918, 993, 936, 731, 25, -452, -463, -959, -166, -881, -599, 814, -136, -959, -501, -925, -66, -768, 105, -645, -180, -989, -2, 914, -580, 308, 13, -435, 795, 214, -333, 337, 834, 732, -575, -797, -574, -59, -785, 617, -484, -926, -734, 838, 345, -78, 963, 333, 813, 47, 83, -243, 751, 412, -520, 976, 967, 382, -526, -406, 847, -846, 523, 599, -687, -342, 13, -878, -326, -926, 690, 123, 752, 573, -404, -620, -743, 623, 691, 724, 986, -96, -715, -745, 227, -995, 563, -402, -716, -399, 631, -735, 446, 300, -155, 54, -387, 630, -443, -501, -277, -279, 573, -707, 532, 571, 473, 664, -395, -508, 695, 32, 95, 345, -856, -518, -145, 506, 139, 41, 787, -422, -440, -259, 555, 737, 66, 302, 217, -668, -168, -294, 999, -111, -332, 273, -690, 598, 17, -158, -451, 681, -253, -861, 453, 872, -80, -945, 855, 881, 821, 392, -351, 594, -968, -802, 651, -749, -258, 31, -937, -38, 23, 288, -641, -812, -108, 583, 576, 392, 526, -941, 184, -759, 156, -138, 439, -827, 401, -449, -420, -258, -217, -34, 187, -716, -118, -661, -930, -898, 386, 605, -489, 476, 934, -5, 123, -709, -497, -773, -494, 152, -835, 331, 971, 277, -614, 126, -248, 234, -370, 63, 699, -834, 184, -778, 863, 315, -678, 707, 267, 807, 521, -264, 336, 245, 29, -627, 320, -517, -215, 559, -783, -748, -25, 775, 448, -627, 256, -959, 941, 398, -703, 728, -807, 721, -855, 423, -290, 317, 165, 201, 194, -940, 427, 643, 302, -958, 733, 43, -101, 153, 939, -325, -312, -193, 100, -735, 415, -103, 126, 900, 162, -79, 61, -707, 722, -330, -425, -245, -137, 511, 947, -154, -569, 404, -724, 856, 64, 776, -513, -878, -837, -323, -803, -399, 772, 102, 469, 132, 173, 263, 509, 408, -268, -307, 58, -912, -752, 505, -626, 325, 623, 329, 806, -810, 42, 812, 228, 303, -81, 629, 764, 986, 792, 748, -578, -411, -703, 935, -604, -656, -80, 471, 229, -227, -137, -360, 322, 780, -400, -528, 28, -405, -498, -514, -316, -173, -862, -833, -904, -412, 148, 285, -732, 79, 348, 459, -562, 920, 225, 975, 645, 574, 455, -271, 955, 237, -309, 534, -42, 492, -134, 860, 718, -678, 336, 82, 919, -561, -37, -455, 191, 940, 833, -87, 410, 997, -307, -190, 831, -125, -633, -519, -262, 414, -993, -25, -738, 224, -333, -390, 932, 277, 691, -40, 534, 795, 608, 619, -637, 343, -262, 877, 833, -799, -15, -426, 281, 916, -459, 898, -388, -474, 312, -481, 979, 725, -204, -971, -626, -578, -867, 318, -617, -855, -595, 954, -766, -851, -299, 63, 467, 532, -324, 219, -260, 261, -77, -825, -600, -525, 924, -971, -332, 865, 765, -197, 487, -421, 80, -24, -691, -767, -221, -217, -566, -469, -183, -910, 923, -679, -210, -549, -288, -655, -705, -929, -416, 111, 519, -323, 467, 100, 162, 851, -887, -253, -522, 3, 995, 403, 335, -37, -61, -430, 487, 412, 962, -511, 269, 527, -415, 964, -879, 836, -581, 732, 875, 508, 55, -22, 795, 760, -664, 10, -810, -744, 907, 237, 976, 599, -196, 411, -680, -720, 274, -82, 166, -427, -455, 914, 593, -778, 462, 399, -886, 565, 349, -858, 974, 526, 579, -476, -566, 287, 999, 823, 301, -832, -46, 551, 198, -39, -601, 806, 457, 968, -591, -297, 186, -899, -819, 872, -351, 788, -43, -912, 581, 521, 204, 994, -775, -752, -771, 397, -733, -393, -832, -489, -641, 276, 280, -394, 866, 42, -228, 692, 391, 315, 292, -969, 449, 911, -173, -415, -140, 383, 676, 25, 996, 346, 125, 553, -725, 557, 203, -804, 94, -129, 995, -446, -719, -288, -697, 455, -783, -560, 956, 461, 469, 596, -593, 265, 823, 321, 259, 635, 551, -921, 260, -554, -618, -953, -946, -874, -270, 33, 606, -692, -602, -95, -698, 263, 46, 708, 110, -191, -240, -519, -142, 940, 974, -910, 912, -900, 524, 952, -303, -428, -198, 375, -880, -982, 482, 334, -285, -658, -71, -196, -192, -47, -879, -806, 496, 799, 826, 74, 959, 829, 639, -962, 325, 89, 527, -392, -334, 536, -30, 250, 991, -797, 824, 431, -346, -865, -689, -418, -929, 252, -483, 328, 411, 938, 754, -746, -27, -794, 61, 414, 693, 849, -734, 407, 53, -288, 953, 170, -830, -860, 431, 803, -382, -296, 36, -322, -824, -154, 999, -862, 148, -597, 74, 618, 840, -75, -754, -45, -79, -375, -652, 470, -697, 703, 632, -726, 382, 336, -656, 903, 250, 722, -114, -509, -306, -565, 8, 630, 417, -25, 609, -904, -595, 612, 509, 531, 835, -329, -753, -964, -283, 711, -836, 91, 164, -617, -513, 588, 415, -482, 995, -223, -881, -995, -346, 804, 435, 796, -874, -284, 148, 559, -655, -576, -79, 853, 808, -741, -667, -207, 732, 237, 601, 79, 231, 759, -387, -468, 438, 513, -742, 818, 631, -6, 367, -488, -400, -34, -860, -373, -96, -406, 54, -688, -865, 944, 817, -474, 476, 305, -470, 865, -892, 187, 77, 467, 317, -915, -616, -863, 154, -512, 635, 462, 519, -700, 223, -193, -670, -250, 736, -82, 125, 734, -742, 393, -94, 863, -3, 93, 8, 556, -11, 387, 561, -212, -501, -580, 639, 455, -56, 356, 152, -829, -873, -178, -577, -173, -579, -139, 505, -349, 747, 731, -49, -60, -179, 684, -19, 548, 556, 683, 790, 316, -878, -372, -250, 454, -909, 732, -27, -176, -906, 371, 794, -722, -221, -314, -860, -321, -422, -119, -657, 603, 915, 449, 284, 594, -673, 413, 101, 218, -732, 400, -501, 764, -182, 557, 937, 996, 818, -267, -739, 635, -314, -566, 881, -822, 623, 592, 611, 510, -874, 817, 501, 405, 855, -705, 905, -216, 897, -424, 224, 397, 621, -456, -373, -780, 617, 381, 508, -208, 758, -869, -593, -465, -600, 784, 207, 498, -156, 611, -626, -656, 156, -782, -710, -563, -436, 176, -508, -571, 933, -656, 365, -899, -662, -380, -865, 722, 149, 555, 346, 340, 622, 503, -502, -516, -295, 782, -773, 554, -161, 569, 837, 121, -696, 962, -97, 793, 921, 589, -397, 296, 645, -138, -288, 578, 665, -935, 780, 668, -125, 545, 519, -759, -97, -188, -991, -777, 443, 900, 706, 339, -671, 185, 144, 899, -165, 105, -235, -979, -74, -138, -593, 120, 759, 785, 584, 961, 248, -55, 322, -473, 94, 34, 440, -466, -381, -589, -399, -367, 687, 947, -446, 223, -136, -515, -949, 885, -200, 779, -112, 962, -196, -597, 200, 306, -163, -656, 751, 749, 479, 128, -625, 249, 967, -522, -833, -54, 206, -694, -546, 497, 554, -189, 463, -839, -606, -639, -690, -844, -595, -490, 717, 706, 508, 741, 773, -138, -327, -158, -376, -283, 481, 493, -286, -436, -421, 19, 713, -763, 325, -185, -983, 674, 948, -258, -282, 830, 534, 411, -344, 757, 628, 327, -299, 497, 737, 434, 759, -849, 666, 367, -597, -390, -241, 331, -405, -11, -984, -645, 456, 230, -940, 951, 3, 962, 338, 756, -837, 200, -861, -568, -587, 448, -81, 126, 507, -773, 860, 476, -700, -574, -230, 468, -297, -346, 584, 796, -783, 315, -891, 985, 313, -70, 775, 116, 43, 36, 812, -788, 624, 645, -323, -912, 701, 222, 691, -158, -491, -610, -890, -65, 596, 48, 420, -836, 40, 651, -268, -964, -86, -430, 344, 73, -573, -841, 207, 910, -300, -404, 610, 419, 692, -693, 47, 337, 614, 950, -250, 506, -153, -646, 401, 60, -103, -298, -339, 117, -840, -57, -250, 791, -448, -597, -102, 821, 238, 460, 946, 837, 378, 258, 941, 683, 944, -996, -402, -260, -109, -452, -33, 176, 483, -835, 479, -322, -884, -740, 496, 635, -201, 122, 819, 333, -131, -133, 709, -841, -960, -277, 616, 59, -14, 920, -295, -341, 684, 446, 700, -95, -324, -549, -108, 145, -682, 546, 434, -378, 589, 716, 188, 940, 312, -60, -829, -620, 541, -289, 79, 855, -420, -811, 426, 577, -572, 547, -1000, -802, -934, -376, 844, -16, 165, -893, 741, -649, 124, -932, 301, -752, 922, 584, -295, -904, -377, 488, -254, 578, -897, 520, -17, 307, -858, -264, 90, -680, 783, 700, 14, 550, 58, -663, -789, -94, -646, 817, -125, 972, -216, -814, -246, -19, 3, 975, 258, -625, -267, -699, 587, 829, 641, -823, -185, 829, -746, -409, -594, -868, 21, 749, -40, -860, 388, -449, -280, -720, -339, 384, -288, -113, -614, 390, 541, 752, 729, -526, -75, -329, -528, -654, 657, -245, 911, -452, -438, 557, -114, 97, -86, 93, 938, 390, 430, 560, 682, -927, 53, -925, 831, -673, -406, 516, 898, 994, 439, -518, -462, -915, 815, 662, -714, -775, 497, -207, 559, 402, -290, -286, 359, 445, -942, -805, 776, 439, -619, -516, 20, -304, 72, 810, -535, 435, -105, 348, -967, 909, 569, -34, 168, -634, 719, 694, 695, 593, -58, 218, -896, 662, -44, -487, -126, -856, 732, -77, -546, 142, -370, 607, 583, -66, 683, 995, -888, 821, -454, -622, 622, 64, 630, -74, -326, -343, 556, 542, 907, -116, -171, -352, 996, -572, -312, -362, 768, 139, -315, -768, 850, -35, 366, -675, 611, -146, -755, -21, -330, 615, -100, 664, 800, 396, 281, 611, 160, -128, 909, 360, -979, -449, -334, -994, -878, 702, 904, 91, 499, -970, 663, 110, -919, 21, 259, 890, -879, 392, -373, 558, -403, 889, -872, 432, -181, 172, -869, 249, 167, 396, -105, 841, -618, 469, -329, -88, 563, -689, -911, -265, -541, 724, -461, -304, 470, 804, 240, 550, 138, -571, -634, 838, -146, -996, -803, -270, 919, 801, 402, 906, -94, 387, -404, -965, 419, 58, 540, 903, 401, -452, 140, -841, -479, 320, -596, 361, 306, -222, 667, 913, 100, 415, -987, 984, 400, -601, -839, 545, 484, -854, 490, -797, -613, 370, 695, 711, -90, 667, -244, 332, 967, 223, -100, -743, -887, -28, -10, 852, -362, 129, 692, 583, -932, -523, -350, 879, -498, 71, -329, -752, -120, -797, 273, -5, -65, 799, -835, -584, 628, 578, -906, -436, 750, -193, 716, -976, -991, 727, -860, -637, 611, 77, -504, -373, 68, 984, -731, 661, 342, 735, -871, -555, -213, 898, -304, 189, 100, 733, 811, -303, -881, -433, -916, 771, -584, -685, 92, -17, -927, -329, 327, -431, 344, -143, 757, 414, 850, 443, -102, -506, 857, -492, 984, 809, -486, 303, 997, -677, 541, -831, -812, -428, -684, -383, 275, 10, -531, 930, 948, -499, 328, 882, -793, -614, -268, -901, -925, 810, -435, -521, -100, -886, 18, 467, -39, -935, -343, 463, 936, -106, -371, -718, -720, 644, 641, -950, 600, 975, -181, 642, -20, -367, -393, -709, 785, -524, 451, 412, 854, 617, -419, 133, -146, -693, 924, 615, -521, -600, -3, -840, -603, -78, 16, -536, -419, 132, -130, 956, -900, 608, -370, -185, 458, -451, 883, 97, -21, 168, -127, -634, -843, 121, -401, 793, -185, -833, -258, -295, 610, 437, 508, -551, 906, 971, 239, -431, 343, -911, -134, -98, -419, 744, -552, 782, -743, -372, -820, -127, 856, 633, -352, 270, -33, 488, -536, -125, -329, -55, -95, -306, 471, 861, 67, -587, 518, 327, -410, -476, -812, -351, 300, -633, 159, 469, 784, -807, -599, 443, 152, -559, -459, -239, -597, -932, 51, -323, -413, 247, -62, -563, -921, -451, 78, 784, -482, -854, -388, -520, -712, 849, 450, -797, 999, -899, -553, 509, -859, 529, -551, -802, -774, -999, 637, 373, 873, 473, -769, 774, 594, -916, -575, 605, 289, -735, -440, -142, 427, 325, 817, 334, 149, -601, -650, -802, -244, -837, -182, 913, -111, 214, -881, 815, 201, 199, -945, 849, -223, 173, -513, 344, 495, -375, 557, -253, -771, 114, -358, -926, 661, -382, 890, -958, -615, 112, 27, -976, 961, -913, -83, -959, 771, 256, 64, -170, 599, 658, 917, 845, 180, -221, 458, -934, -790, -72, 992, 704, -400, 763, -170, -532, 708, -368, -836, -63, -257, -461, 260, 375, 227, -609, -710, 30, 853, -814, -503, 923, -220, -286, -230, -149, -313, -533, -170, 866, 177, 18, -776, 580, 596, -474, 598, 833, -658, -260, 253, 738, 415, -737, 303, 716, -695, 469, -340, 225, -105, -156, -216, -496, 491, -592, -615, 528, -637, 932, 8, 410, 705, 129, -896, 837, -396, 175, -288, 317, -910, 901, 710, 785, 274, 978, 272, -304, -604, -819, -128, -67, -120, 60, -440, 195, -606, 521, -890, 834, 982, 141, 865, -309, -711, -441, -404, -30, 322, 398, 396, 497, -528, -334, 751, 543, -775, -83, -375, 258, 581, -334, 111, -636, 668, -512, -476, 769, -809, 725, 475, 827, -341, 70, 11, -507, -755, -255, 870, 508, 261, -124, -33, 289, 581, 554, 902, 384, 862, -289, 644, 988, 990, -825, 366, 43, -478, -652, 825, -83, -749, -338, 432, -677, -418, 575, -140, -287, -124, 279, 12, 670, 598, -83, -259, -769, -799, -960, -241, -471, 558, 444, -295, -826, 294, -563, 459, -390, 373, 357, 106, 519, -928, 360, 601, -638, 352, 937, 199, 480, 791, 531, -329, -950, -502, -234, -843, 413, 781, 467, -196, 862, -111, 651, 153, 41, -379, 186, -424, 879, 80, 466, -60, -298, -925, -278, 106, -897, 233, -149, 350, -712, -939, -66, 512, -217, -828, -620, -514, -954, 288, 216, -933, 489, -822, -51, -826, -720, -711, -374, -486, -620, -203, 633, -456, 868, 964, -221, -781, -233, 472, -895, -450, -345, 979, 273, 641, 362, 481, 978, 991, -713, -227, -92, 314, 653, 250, -86, 575, 862, 512, 189, 825, 757, 716, -714, -643, -451, -491, -416, 725, -4, 235, 437, -411, -779, 670, -732, -30, -85, 184, -304, -530, 303, -526, -899, -473, -90, 364, -146, -102, 504, 983, 212, -148, -588, -20, 928, -592, 86, 615, 58, 139, 898, -988, -515, 504, 171, 553, -99, -891, 671, -51, 120, -846, -178, -730, 699, -820, -493, 601, -902, 800, -916, -3, 613, -949, -951, 765, 785, 411, -699, 810, 816, 386, -310, -81, 283, 540, -725, 751, -182, 697, 903, -494, -780, 109, -775, 782, 31, 241, -745, 51, 882, -642, -279, -282, 89, -754, 110, -491, 960, 134, 62, -783, -56, -721, 166, 750, 302, -117, 497, 838, -887, 577, -304, -190, 820, -599, 689, -605, 476, -612, -442, 302, -314, 282, -231, -513, -229, 614, 273, -95, 725, -693, -623, -615, 237, -741, -151, -885, 654, 926, 111, -544, -252, 430, -435, -59, 374, 585, -862, 217, -368, 121, -199, 25, -515, 109, -20, -426, -698, 410, -438, -367, 461, 502, -336, -353, 632, -95, 505, 374, -257, -999, 217, 432, -844, 301, -477, 605, 104, 818, -135, -293, 169, 224, -408, 746, 356, -590, 639, 618, 553, 921, 727, 239, 544, -159, 401, 509, -807, -743, -543, 447, -824, 95, 36, 802, -426, -40, 975, -365, -368, 833, 270, -865, 521, 583, 539, -357, 610, -145, -1, 286, 594, 235, 571, -697, -530, 248, -181, 668, 710, 972, 195, -155, 964, 717, 697, -519, -670, 400, 374, 63, -594, 743, 726, 668, 917, -39, 304, 864, 838, 886, -95, 426, 974, -510, -300, 520, 71, 139, 549, 999, -686, 885, -644, 620, -66, -994, 126, 340, 819, 815, 788, -501, -873, 411, -439, 868, -474, 169, -407, -225, -717, 436, 964, -729, -496, 941, -11, 277, -586, 363, 256, 666, 706, 801, 551, -494, -999, -564, 528, -299, -448, -712, 402, -27, 339, -884, -564, 951, 514, -64, -453, -533, -726, -718, -523, -615, 21, 182, -477, -248, 569, -115, -671, -72, 732, -739, -10, -976, 103, -407, 178, -520, -929, 562, -661, -238, -912, 273, 930, -221, -867, 228, 907, -659, 989, 171, 297, -69, -711, -291, -137, 983, -743, -762, -468, 226, -740, 841, 162, 540, -635, -7, 971, -196, -640, -154, -817, 867, 491, 569, 212, 554, 48, -299, -681, 213, -550, 130, -759, -949, -465, 684, 605, 250, -636, -585, -482, -670, 855, -778, -870, 558, 267, 142, 737, 839, 337, 826, 874, -806, -810, -223, 204, 68, 986, 57, -253, 15, -385, -333, 237, 616, 17, 463, -166, 391, 251, -840, -334, 258, 385, 591, -207, 386, 684, -240, 333, -18, -525, 67, -742, -849, -57, 832, 664, 21, 978, 162, 570, 963, 507, -968, 221, 269, -373, -433, -777, -908, 442, -323, 458, -94, -673, -400, 252, -26, 163, -392, 340, 206, -619, -108, -41, -987, -462, 187, 118, -699, -713, -790, -694, -791, -599, -123, 386, 463, 67, -990, -475, 786, 686, 6, -835, 800, 536, 556, -818, -639, 509, 806, 861, 721, 431, -359, -799, 534, 735, 75, -658, 747, 625, 12, 117, -282, 345, 378, 324, -38, -723, -486, -681, 205, 835, 412, -427, -47, -729, 918, -388, 551, -277, -400, -381, 513, 535, 842, 995, -812, 103, 244, -826, 369, 892, -340, 330, 776, 826, -446, 587, 690, 138, -663, -546, 650, -135, 14, -978, 688, 17, 128, -604, 563, 513, -115, 637, -996, 913, 596, -603, -525, 475, 960, -654, 13, -626, -171, 2, 995, 38, 913, -769, 611, 183, 509, 869, -589, 911, -572, -752, 218, 694, 390, -907, -888, 601, -368, -143, -371, 189, -389, 604, -362, 523, 952, 489, -913, -902, -184, -19, 834, 872, -888, 337, -116, -135, 810, -159, -329, 338, 397, 140, 231, -357, -572, -792, 397, 718, 699, -73, -760, 751, -558, -589, 244, 17, -36, -997, -873, -420, 972, 567, -363, 844, -395, 23, 136, 890, 407, 840, -799, -22, -566, 826, 556, -166, 556, -662, -405, -549, -292, -538, 131, 306, -503, -987, -142, 148, -717, 429, -462, -127, 577, -36, -893, -152, -340, -97, -958, -544, -671, 682, 206, -667, 159, 775, -180, 460, 274, 345, 621, -470, -428, 877, 191, 368, 438, -78, -590, 783, 968, 208, 901, -300, -361, 856, -353, -150, 668, -950, -554, -819, 33, -562, 420, 793, 8, -252, 63, 458, 911, -644, 744, -464, -17, 139, -478, -436, 328, 605, 833, -21, -779, -717, 546, 987, -757, -199, 426, -925, 996, -29, 679, -912, 60, -618, 506, 855, -717, 648, -826, -517, 784, -191, 141, -682, 80, -442, 764, 546, 980, -588, -830, -860, 547, 5, 400, -395, -591, -876, 36, 894, -525, -138, 125, -143, -458, -490, 609, 817, -509, 347, 298, -38, 620, 82, 504, 51, -325, -945, -862, -605, -487, -83, 138, -606, 531, 412, 127, -462, 709, 828, 595, -68, -309, -975, -576, 548, 345, 94, 355, 375, 791, 368, 346, 980, -465, -179, -318, 647, 128, 213, -180, 220, -523, 710, -121, 885, -744, 51, 835, -91, -948, -541, -71, 543, -636, 518, 32, 500, 547, -596, -995, 996, 98, -156, -399, 47, -889, -589, -291, 521, -359, 351, -434, 94, -695, -81, -16, 104, -465, -781, 119, -482, 231, 438, 58, -314, -784, 482, 523, -209, -461, 583, 864, -626, 394, -566, 510, -253, 154, 808, -774, -812, 220, -736, 251, 376, -434, -430, -813, 870, 464, 525, 953, 691, 87, -232, -367, -229, 343, -538, 579, 38, -501, 144, -332, -48, -939, 391, 649, 51, -380, -134, -330, -538, 632, 531, 720, -697, -255, -877, 101, -341, -178, -664, -991, -305, 319, 154, -321, -179, -662, 27, 898, 32, 885, 456, -189, 836, -977, -192, -720, -330, -186, -63, 249, 601, -615, 872, -106, -608, -547, -745, -869, 54, -106, 679, 301, 537, 974, -80, -531, -716, -621, 754, -910, 490, -916, -852, -224, 580, 29, -29, -730, 421, 833, -986, -502, -92, 21, 643, 749, -834, -827, -812, 555, -821, 598, 100, 913, 425, 343, -41, 388, 400, 825, -953, -838, -692, 911, 745, -267, 802, -840, 657, 638, -317, -944, -290, 960, 500, 954, -718, 712, 768, 813, 908, -550, -108, 652, -98, 985, -410, -803, 302, -144, -284, 670, -362, -81, 36, 481, 377, -360, -577, 262, -925, -335, -223, 927, 841, -144, 565, 826, -286, 187, -670, 771, -322, 852, -767, 545, -121, 261, -312, 420, 754, 645, 635, -402, 397, -287, 113, 637, -595, 226, 784, -475, -528, 229, 550, 758, 65, 340, -296, 706, 635, -623, -401, 325, 988, 65, 487, -994, -607, -397, -40, -309, 585, -343, 724, 196, 570, 990, 395, 581, -302, -582, -29, 896, 764, 533, -842, 700, -599, 409, -964, -316, 834, 705, 27, -424, -136, -442, -433, 685, 774, -62, -712, -85, -435, -311, -420, -788, -965, 317, -783, 648, -662, -387, -314, 514, 513, 1000, -56, 637, 134, 747, -314, -982, 360, 284, -15, -21, 407, -192, 124, -693, 869, 269, -669, 721, -340, 799, -834, -384, 622, -446, -580, -393, 75, 735, -492, -22, -590, -388, -419, 912, 709, -955, -303, 853, -272, 807, 949, 613, -623, -794, 115, -791, 741, 327, 176, 668, -101, 933, 741, -929, 928, -361, -420, -222, 372, 741, -117, -758, -269, 828, -951, 683, -964, -910, 791, 890, 174, 849, -887, -657, 246, -318, 238, 978, 324, -185, 768, -567, -275, 405, -223, 810, -736, 457, -176, 771, 85, 833, 55, -320, -711, 357, -982, 968, 719, 593, 673, 42, 296, 203, -492, 877, 246, -490, 793, -455, -339, -632, -861, -128, -47, 588, 535, -63, 489, 681, -658, -18, -149, 579, -52, 263, -717, -823, -819, 90, 513, -164, -645, -227, -870, -106, -482, 470, 329, 38, -233, -971, -406, -863, 965, -529, 476, -682, -85, -553, 363, 963, 328, -716, -555, -176, 710, 458, -801, -863, 695, 508, -93, -203, -55, -228, 205, -173, -195, -124, 991, 917, -392, -223, 423, 519, -555, -256, 526, 565, -619, -685, -459, -850, -464, -189, 653, 341, 723, 356, 574, 38, -59, -407, 815, -886, 208, 403, 352, -888, 92, 420, -115, 862, 708, 634, 856, 300, -899, 16, -814, -627, -451, -246, -128, 149, 512, 620, 278, 487, 470, -782, -862, -351, -308, 620, -87, 703, -635, -411, -958, 620, -938, -575, 514, 620, 279, -401, -706, 548, 336, 2, -105, 774, -850, 725, -253, 421, 5, 335, 799, -784, 420, -847, 117, 174, 602, 128, -317, -9, 644, 284, 650, -301, -747, -212, 606, -684, -267, 764, -252, -508, 446, 25, 994, 853, 455, -177, -740, 801, -565, 403, 310, -568, -289, 31, 354, -399, 853, -673, -203, 698, 123, -144, 509, 730, 864, -704, -275, 332, -376, 932, -310, -750, -956, -534, -607, 856, 834, -581, 826, 852, -146, 450, -316, 707, 704, 620, -56, -460, -189, -552, 152, 990, 758, -903, -848, 742, 708, 291, 663, -707, -25, 239, -890, -981, 153, 541, 133, -38, -203, -191, 358, 336, -398, -812, 385, 274, 68, 433, 75, -310, 36, -56, -450, -6, 565, -727, 559, 921, 480, 709, -150, 212, 979, 697, 562, 931, 445, -271, 462, 344, 201, 600, 40, 845, 402, 251, -896, -515, 231, -122, -43, -886, 110, 289, -554, -656, 548, 492, -834, -968, 946, 890, -693, -904, -699, -9, 790, 406, -485, 283, -138, 627, 294, 582, -769, -490, 507, 36, -837, -103, 975, -903, 956, -937, 184, -578, 626, 978, -435, 937, 429, -776, 854, 101, -193, 370, -678, 400, 171, 343, -803, 892, -616, -530, 75, 788, -639, -116, 851, 295, -123, -238, 829, -821, -927, 46, 27, -473, -511, -373, 73, 881, 279, -645, 577, -466, 959, 33, 253, -990, 39, -654, 28, -761, 959, 320, 668, -675, -252, -564, -954, -396, 259, 174, 747, 851, 156, 245, 771, -656, 537, -961, 793, -799, -708, 127, -409, 954, 462, 193, 718, -315, 357, 775, -690, -363, -738, -621, -77, -362, 203, -536, 170, -729, 654, -33, 51, -164, 535, -634, 390, -582, -598, -290, -699, 458, -257, 168, 112, 736, 334, 805, -803, -39, -811, -204, 551, 182, 642, 653, -374, 424, 931, -941, 750, 204, 697, -840, 455, 255, 607, -145, 305, 945, -279, 15, -174, -651, 310, -785, -792, -693, -474, -881, 819, -914, 121, 780, -298, 717, -709, -107, -550, -272, -539, -50, -575, -639, -782, -139, 827, -672, -31, 624, 872, -446, -347, 240, 461, 955, -97, 433, -614, -976, 237, -797, -950, 31, -348, -184, -164, 903, -492, 907, 437, -913, -780, 833, 193, 452, -987, -183, 609, 782, -618, 787, -314, -345, 457, -417, -167, -186, -69, 66, 834, -430, 443, 836, -597, -506, 359, 419, 919, 163, 214, -197, 56, 333, 108, 89, 444, 709, -797, -562, 795, -223, -459, -371, -802, 724, 167, -994, -492, 564, 984, -332, 806, -943, -844, 9, 960, -211, 184, -239, 985, -341, -440, 443, 332, 982, 9, -924, -457, -302, 338, -430, 604, 710, -816, -502, 937, 951, -981, 225, 559, 95, 936, 320, 806, -299, -947, 967, -717, 995, -857, 505, -262, -564, 539, 122, 472, -417, -749, 893, 668, 295, 211, 959, -250, 62, -837, -523, -938, -951, 138, -866, 906, 822, -788, 817, -41, 492, -535, 2, -910, 469, 333, 875, -532, 580, -655, 932, -240, 486, 245, 145, 682, 313, -32, -979, -371, -742, 255, -975, -547, 357, 727, 845, -527, -310, -876, 937, -354, -637, -186, -69, 341, -424, -40, -295, -103, 962, 167, -814, 959, -507, -429, 158, 565, -967, -610, 860, -638, 18, -596, 166, 708, 66, 565, 511, 265, -605, -532, 8, -99, 673, 381, 77, 554, -144, 283, -662, -168, 179, 607, 212, 591, 167, -205, 24, -593, 231, -757, -612, -817, 295, 583, 778, 965, -275, -57, 597, 947, 965, -141, -355, 17, -591, 812, 716, -184, -176, -751, 837, -41, 135, -385, 364, -698, 827, -520, -923, -738, -41, -90, 998, 354, 266, -372, 668, -144, -713, 902, -435, -376, -584, -499, 936, -16, 347, -955, -728, 530, -585, -831, -981, -447, -845, -100, 973, 786, -924, -157, 791, -482, 89, 423, -33, -610, 906, -133, 435, 934, 472, -664, 35, -240, -166, 330, -70, -256, -727, 576, 160, 879, -79, -407, 312, 390, 271, 120, -971, 187, 123, -493, -709, 56, -662, 640, -736, 696, 399, 372, -37, -942, -552, -403, -59, -615, 990, 547, 483, -418, 169, -215, -10, -612, 581, -438, 426, 85, 449, -762, -652, 3, 145, 491, -649, -602, -560, -874, -698, -236, 919, 486, 835, -769, 56, -717, -315, -759, 351, -315, 993, 498, 177, -598, -800, -471, 346, -91, -283, 974, -756, -735, 864, -52, 98, 931, -749, 658, -352, 727, 811, -987, -429, -968, 98, -198, -473, -275, 167, -8, -688, -845, -39, -455, -415, 360, -831, -29, 750, -977, 287, 439, 353, -976, -344, -563, -677, 209, -292, 377, 476, -564, -863, -34, -521, 138, 15, -884, 91, -949, 627, 947, 516, 95, -690, 532, -448, -875, -40, 406, 316, 891, 115, -566, -701, -848, 126, 763, -127, 489, 516, -297, 701, 756, -308, 372, 871, 841, 369, -83, 653, -711, 698, -2, -337, 239, 2, 643, -608, -483, -265, -340, 800, -285, 7, 886, -99, 548, 590, 11, -726, -379, 57, -909, 627, -633, -641, -4, -390, 438, 328, -925, -796, 900, -679, -850, -384, 287, -428, 972, 467, 230, -8, 164, 986, 54, 776, -220, -573, -262, -726, -152, -696, -504, 126, 73, 691, -712, 759, -451, -309, -393, -679, 199, 443, -146, 963, 517, 958, -217, -205, 430, 809, -538, 13, 590, 334, -554, -766, 554, 460, 45, -413, 693, -67, 204, 853, 362, -859, -214, -252, -438, -345, 927, 666, 250, -101, -931, -235, 495, 927, -907, 900, 300, -361, 846, -544, -541, 158, -804, -249, 164, 952, -12, 898, -428, -375, 373, -611, 20, 789, 144, -358, 365, 371, -879, -205, -495, -868, 827, -213, 976, 283, -178, -402, -822, -256, 553, 326, -219, 169, -176, 630, -303, -809, -151, -603, 511, 304, 540, -806, 721, -145, 713, 600, -748, 881, -964, 3, 942, 854, -704, 112, 843, 132, 78, -833, 377, -3, -941, -685, 689, 663, -986, -206, 736, 407, -709, 763, -627, 798, -933, 58, -347, 29, 9, -373, 445, 852, 40, -66, -46, -248, 58, -157, -852, -906, 269, -769, -547, -157, 218, 70, 892, 197, 27, -231, 534, 705, 275, 67, 680, 872, -418, -565, 121, 405, -895, -437, -182, -441, 902, -292, 389, 24, -145, 879, -954, -404, 464, -39, -644, 988, -860, -240, 733, -573, -734, 901, 309, -247, 18, 798, 635, 101, 995, 971, -99, -889, 750, 13, -864, -496, 329, -634, 533, 902, -962, -423, -479, -955, 236, 388, 767, -873, -545, -980, -430, 923, 118, 774, -592, -516, 27, 890, -231, -169, -203, -988, -295, 571, 271, 309, -95, -247, 745, -259, -174, 406, 432, -786, -679, -323, 305, 896, -110, 755, 43, -335, -341, 281, 655, 433, 7, -966, -948, 346, 542, -423, -107, 475, 625, -14, 79, 426, 887, 791, -663, 783, 133, 924, 486, 314, 156, 415, -532, 496, -399, -982, 843, 239, 249, -64, 653, -206, -748, -492, -916, -950, 403, 444, -301, 739, -228, -468, -599, -390, 57, 47, -471, -302, -847, -841, -922, -297, 33, -709, -210, -454, -831, -527, -659, -360, -359, 196, -448, -255, -337, 255, 727, -274, -354, -627, -870, -167, 760, -948, -715, -476, 556, 544, -766, 636, 784, 882, 335, -583, 187, -772, -183, 76, 737, -59, 272, -41, -556, 72, 852, -83, -866, -366, 785, 900, 998, 204, -642, 124, -866, -858, 288, -167, 96, -577, -12, 117, 448, -666, -207, -749, -475, 508, 586, -221, -525, 123, -166, 7, -343, -253, -408, -515, 523, -290, 691, 182, -936, -469, -30, -1, 136, 150, -739, 464, 176, 970, -664, 408, 87, 90, -95, 38, 330, 880, -918, 146, -282, 477, -612, 202, 765, 110, 605, 965, -675, 580, -423, 868, 515, -766, -997, 967, -844, 85, -868, 347, -949, -415, -754, 664, 51, 128, -684, 15, 112, 462, -480, -226, -597, -607, 73, 660, -502, -139, -540, 859, -105, 146, -407, 675, -334, -307, -466, 550, -51, 471, 223, -846, 47, -400, 20, 822, 204, -343, 894, -152, -347, 582, -791, -330, -36, 890, 521, -620, -87, 339, -558, -117, 647, 54, 217, 911, 475, -737, 337, -572, -50, 476, -194, 160, 507, 947, 658, -761, -115, -442, 675, 93, 509, -351, 195, 16, -69, 459, -643, 454, -582, 728, -629, 461, 810, 634, 208, -671, -964, -524, 674, 918, -159, -105, -427, 473, -477, -719, -306, -539, 517, 442, 894, 125, 320, -443, -593, 364, 503, -936, -670, 651, -601, -586, 502, -572, -873, 457, 647, 747, 940, -358, 549, 333, -387, -448, 533, 809, -180, 856, -437, 772, -325, 910, 981, 511, -841, -315, 496, 458, 26, 324, 245, 596, 189, 25, -938, 407, 293, -734, -703, 202, -528, 802, -362, -202, -233, 312, 14, -593, 132, -301, -783, -355, 272, -740, -180, 742, 64, 429, 716, -40, -779, 627, -713, 935, -428, 325, -774, 578, -67, -45, 670, -499, -781, 314, 941, 519, 132, -729, -288, -386, 404, 272, -963, -517, -932, 172, 953, 711, 951, 596, -243, 270, 124, -205, 981, -305, 334, -16, -815, 680, 909, 405, -828, -692, 970, 13, 858, -607, 118, -663, 438, -839, 717, 605, 108, 149, 714, -842, 435, 569, -58, 563, 105, -195, -875, -484, 589, -584, 526, -727, 939, 871, 304, 997, -913, 543, 878, -490, -317, 465, 284, -968, 206, 317, -372, -12, 729, 662, -925, -373, -537, 652, -393, 468, 602, 483, 771, 453, 290, 366, -28, 473, 748, -840, 589, 946, -923, 869, -933, -599, -546, 140, -517, -596, 822, 4, 491, 606, 37, -889, -245, -773, -841, -34, 158, 563, 239, -144, -468, -722, -151, -88, -576, -864, -959, -615, -599, -602, -934, 181, 978, 564, 612, -483, -104, -354, 943, -714, 132, 496, 182, 562, -861, 513, -471, -303, -830, -717, 705, 99, 814, -415, -69, -864, -63, -375, 427, 176, -151, 586, -211, -322, 91, -870, 302, -70, 941, -891, -991, 875, -827, -557, 795, -734, 58, 612, -337, -122, 115, -612, -358, -278, -603, 417, 770, 564, -892, 854, -512, -816, 482, -192, -52, 370, -871, 15, 795, -389, 758, -518, -944, 932, -333, 889, 161, 786, -113, -7, -928, -98, 792, -579, 310, 554, 305, -18, 999, 876, -292, 584, 19, 332, 360, 392, -636, 490, 425, -967, -959, 183, 753, 819, -583, 126, 937, 494, -312, -991, 470, 918, 78, 488, -915, 678, 353, 956, 101, -937, 151, -905, 118, -110, -838, 962, -154, 664, 686, 437, -618, -384, -300, 130, 664, 195, -259, -752, 952, -343, 144, -916, -910, -272, 12, -222, -60, 869, 183, 71, -915, -350, -608, -712, 180, 314, -521, 353, 273, 578, 723, -624, -482, -156, -433, 157, -735, -431, -22, 512, -920, -615, 582, 129, 58, -881, -530, -627, -238, 65, -929, 65, -256, -664, 346, 858, -975, 544, -410, -9, -485, 146, -128, -96, -405, 422, -112, 20, -611, 702, 943, 983, -667, 965, -171, -950, -942, -528, -484, 615, -149, -777, 891, 80, -473, -866, 806, -633, 168, 386, 810, -421, -755, 911, 560, 899, -572, 865, -445, 902, -517, 134, -165, 373, 842, 263, -653, -777, 497, -514, 431, 95, 990, 271, -405, -908, -931, -118, -966, 344, 337, -319, -455, -702, 811, -99, -466, -909, -487, 222, 460, -613, 794, -74, -393, 938, 746, 479, 183, 759, -675, -876, -513, -884, -427, 704, 560, -690, 438, 303, 815, -639, 47, -662, -424, -381, -686, -252, -794, -519, 41, -222, 167, 301, 802, -18, 165, -841, 352, -207, 924, 272, 800, -878, 603, -989, -96, -402, 932, -604, -538, 360, -670, -746, -786, -216, -901, 22, -550, -72, 53, 946, -718, -130, 488, 999, -136, 12, 578, -15, 431, -2, 752, -196, -849, 676, 559, 332, -492, 843, 203, 795, -586, -818, -841, -163, 200, 341, -287, 122, 39, 501, -912, -486, -544, -194, 787, 797, 547, -124, 818, -389, 774, 531, 80, 524, 291, -949, -489, 484, -514, 641, -98, -419, -165, 8, 462, -706, 211, -903, -233, -279, -782, -476, -690, 751, -770, -769, -945, 854, 462, -557, -708, 871, 777, 771, 241, -180, -864, -929, 572, 656, -75, -160, 837, 991, 23, 69, 276, 31, 23, -258, -107, 51, 992, 871, -764, -60, -539, -428, 382, 15, -23, -790, 113, 694, 619, 598, 299, 896, -697, 765, -113, 414, -25, 773, -52, 309, 992, 232, 852, -884, 874, -194, 836, 317, 564, -535, -790, 763, -183, -430, -830, -961, -142, 75, 65, 395, 153, 451, -948, 606, -913, -80, 776, -519, -416, 369, -737, -812, 616, 207, 60, 853, 517, 695, 274, -870, -578, 907, 616, -391, -175, -461, 792, 117, -155, 899, 823, -98, 507, 763, -691, -621, 964, -237, 375, 65, 315, 156, -487, -875, 883, 114, 125, -678, -34, 743, -406, -693, -534, -944, 208, 959, -675, -264, -728, 354, -283, -630, 1, -440, 328, -116, 690, 89, -618, -709, -247, -368, -567, -698, -811, -317, 940, -719, -967, -357, 958, -770, -66, -210, -185, 728, 122, -391, -622, 937, 255, -833, 866, 791, 525, 546, -384, 346, -274, 636, -560, -722, -924, -946, -523, -159, 16, 159, 238, 921, 289, -39, 902, -482, -548, -94, 524, 251, 15, 472, -723, 880, 307, -16, 373, 952, -19, -889, -872, -579, -403, 73, 88, -388, -413, 457, 953, -235, -791, -942, 895, -347, 163, 216, 857, 43, -418, 626, -760, -898, 640, 114, -278, -390, 651, -988, 96, -92, 510, -476, 770, 702, -542, -97, -891, 76, -242, -598, -565, -586, -64, -637, -784, 70, -798, -808, 620, 502, -580, -995, 604, -933, -135, 384, 453, -549, -229, -627, -573, -82, -519, -533, -711, -120, -881, -196, -634, -594, -124, 258, 284, -550, -475, -406, 798, -169, 103, 704, 308, 77, 157, -789, 134, 142, 160, 889, 90, 357, 17, 639, 139, 220, 351, -975, -903, -692, 263, 211, 814, 365, -302, -730, 778, -565, 815, 627, -576, -505, 367, -691, 144, -860, -488, -79, -117, -918, 287, 444, 91, 398, -643, 148, -821, -258, 799, 495, -732, 584, 920, -332, -261, 930, 776, 130, 644, 260, -876, -454, 112, 592, 11, -461, 230, -707, -565, 464, 62, -15, 872, 752, 401, 896, -669, 438, 735, 313, 62, 978, 532, -353, -61, -55, -877, 741, 781, -479, -443, -457, 260, -942, -286, 157, -930, -557, -445, -294, 515, -943, -590, 749, 713, -163, -721, -629, -767, -505, -800, -366, 637, 468, 94, 601, 508, -592, -666, -786, -367, 432, 558, -124, -404, 113, -886, 156, 739, 306, -941, 687, -360, 27, -321, 52, -84, 525, -547, -358, -819, -273, 134, -286, -95, 835, 890, 672, -658, -159, 347, 652, 953, -452, 257, -308, 514, 511, 845, 950, -353, -255, -252, 705, 573, -334, 847, 133, 460, 75, 401, -86, 131, -714, 194, -855, 546, -528, -281, 828, 862, 376, -202, -862, 14, 262, 574, 675, 387, -188, 847, -766, 981, -339, 697, -39, 137, -403, -364, -916, 909, -378, -81, -346, 865, -103, 465, -427, -430, -184, 172, -560, -937, -216, -957, -925, -446, 934, 403, -548, 879, 496, -882, 300, -831, 443, 114, 252, -442, 972, 228, 419, 693, 652, -707, 885, 946, 108, -493, 896, -750, -389, -733, 233, -541, -894, -363, -581, 770, 950, 580, 909, -717, 657, -750, -94, -541, 199, -534, -552, -810, -825, 929, 827, -945, 458, -710, -745, -896, -123, 316, -616, 389, -282, -644, -941, 431, 712, 9, -948, 845, 908, -638, 407, -811, 501, -541, -986, -95, -927, -43, 104, -707, 396, 947, 803, 622, -645, -707, 935, 454, -447, 494, 893, 662, -659, 40, -428, 796, 704, 478, 316, -170, 599, 842, 568, -61, 404, -221, -204, 94, -717, -59, 79, -424, 696, -24, -850, 561, 473, -911, -850, 60, -80, -589, -16, -74, -736, 642, 59, -143, 531, -455, -188, -679, 193, 852, -769, 14, -898, 683, -950, 338, 340, 448, -684, -116, 31, -101, 239, 349, 712, 848, -709, -214, 439, 634, -494, -90, 170, -254, -491, -593, 623, 179, 254, -371, -988, -758, -109, 875, 552, -574, 630, -109, 354, -889, 776, 201, -936, -6, -468, 978, -466, 783, 76, 322, -420, 764, -194, -292, -788, 654, 814, 962, -826, -817, 292, 412, 899, -261, -729, -365, -42, 349, 917, 428, -855, 154, -30, -28, -897, 843, -122, 811, 581, 831, 180, 385, 867, -990, 400, -717, -773, 321, -953, 502, -852, -648, 46, 608, -617, 641, 947, 886, -919, -144, -430, -270, 92, 27, 306, 522, -97, -555, 485, -651, 997, 730, -717, 533, 807, 89, 829, 541, -885, -316, 167, 414, 292, 90, 792, -804, -757, 684, 1000, 856, 983, 456, -511, 609, -699, -995, 457, 375, 487, 480, 827, -814, 867, -416, -81, 202, 530, -693, -409, -981, -696, -869, -677, -526, -126, -939, -785, -842, 364, 429, 157, 518, -995, -417, 457, -556, 60, 330, -270, 850, -487, 738, 46, 475, 997, 703, -903, 328, -662, -185, -564, -284, -767, -720, -103, -585, 164, 37, 909, -772, -192, -479, -238, 231, -627, -694, -356, -441, -887, -531, -473, -476, 375, -406, -589, -133, 75, -320, 304, 146, 185, 772, 35, -538, -306, -633, -730, -423, 834, -235, 735, 993, 902, -11, -385, 889, -343, -116, 505, 673, 757, 738, 453, -408, 42, -849, -726, 586, 461, -83, 744, -439, 962, 542, -420, -192, -20, -494, 70, 114, -397, 984, -306, 84, 43, -599, -860, 543, -949, -78, 335, -785, 156, -909, 896, 145, -602, 584, -681, 359, 227, -868, 717, -923, 508, -730, -801, 714, 557, -133, 602, 301, 574, 839, -938, -426, 589, 329, 201, -754, -670, 337, 292, -416, 134, 651, 325, -263, 42, -588, 807, 108, -316, 128, -314, -225, 158, 415, -208, -913, -433, 586, -992, 536, -802, -480, -628, -784, -73, -515, 908, -34, -269, -37, 46, -123, -320, 727, 443, -381, -647, -715, -427, -788, 910, 275, -143, -722, 568, 743, 11, 265, -459, -266, -122, 68, 189, 228, -306, -463, -113, 488, -633, 479, -875, 909, 916, -947, 956, -562, -984, -327, -473, -90, -48, 131, -179, 97, -450, -788, -482, 832, 413, -35, -857, 24, 124, -850, 788, 9, 170, -86, 400, 685, 763, -543, -595, -175, -793, 171, 165, 770, 117, 801, 289, 942, 81, -566, -751, -449, 448, 220, 202, 908, -833, -190, 537, -425, 262, 966, -622, 883, -714, 494, 284, -621, 218, 609, -663, -883, 912, -689, 287, 321, 42, -874, -983, 423, 809, -205, 586, -27, -263, -958, 541, -66, 437, -159, 374, 729, 83, 311, -639, 443, -627, 698, 852, -231, 56, -322, -922, 223, -839, -510, 586, -143, -107, 203, 792, 413, 62, -543, -858, 913, -895, -78, 465, 810, 67, -450, 969, -463, -253, 952, -583, -787, 1000, 312, -572, -503, -948, 737, -592, -911, -547, -516, 671, 887, 352, 439, -187, -830, -21, 102, -355, -219, -981, 805, 885, 242, -667, 567, 755, 984, 13, -817, 732, 915, -746, 733, 684, -971, -374, -60, -861, 43, 204, 970, -988, -945, 394, 143, -763, 743, 482, 456, 47, 523, 469, -862, -53, -939, 562, -784, 973, -292, -854, -176, -459, 633, 75, -358, 623, -309, -867, 125, -860, -936, 46, 172, 61, -707, -172, -432, -646, 179, -874, 752, -541, -461, 656, -596, 507, 354, -78, 414, -364, 756, -902, -294, 534, -370, -748, -525, -718, -738, -67, 319, -381, -408, 278, -581, 717, -87, 90, -705, -244, -296, -576, 724, 360, 529, -686, 285, -305, -169, -977, -20, -940, 872, 352, 79, 823, 328, 630, 973, -474, -350, 981, -956, -386, -99, 334, 754, -613, -165, -220, 627, 775, 140, -61, -389, -61, -575, -836, 30, 952, 503, 909, -524, -893, -656, -487, -206, -379, -699, 355, -76, 340, 645, -195, -117, 675, -389, -720, -26, -118, -587, -876, -815, 620, 848, 944, 513, -799, -220, -895, 835, 40, 966, 806, 768, 474, -62, -569, 900, 81, -438, -853, -246, 98, -749, 866, 640, 413, -766, 983, -885, 636, -969, -144, -949, 341, -714, -556, -134, -759, -496, -202, 750, 894, -300, -178, 610, -450, 8, 70, 403, 13, -824, 25, 578, -740, 456, -291, -479, -125, -512, 950, 734, 524, 657, 624, 67, -695, -887, 964, -472, -45, 435, -827, 308, 772, -897, -242, 533, 320, -667, -538, -430, -477, 537, 376, 318, 410, -456, 946, 976, -116, -78, 368, 439, 685, 724, 310, 75, 711, -808, 524, 104, 398, 821, 503, -731, 151, 236, 201, -106, 680, -786, -318, -2, -394, -665, -564, -191, -813, 300, 882, -375, -723, 577, 872, -209, -843, -259, 684, 472, -358, -118, -903, -480, -162, -140, 199, 10, 849, 547, 974, -77, -589, -513, -54, -339, 645, 672, 734, 587, -896, 693, 91, -536, -465, -370, -738, 119, -409, -1000, -327, 991, -167, -971, -939, 797, -578, -142, -890, 750, 238, -966, -218, -54, -672, -337, -887, -111, -400, -167, 545, 15, 78, 325, 635, -740, 342, 520, -408, 326, -360, 369, -638, 84, 594, -739, 304, 235, 415, -771, 310, -454, 722, 669, 845, 879, 265, -714, -797, -309, 857, -477, 332, -706, 942, -530, -970, 364, 543, 918, -688, -436, 200, -729, -544, 801, -248, 238, 167, -315, -556, 711, -137, 589, 835, 912, -326, -783, 392, -378, -24, 811, 454, -707, -634, 509, -124, -153, -168, 261, 607, 543, 918, -922, 745, 697, 86, -411, -902, -570, 88, -474, -469, -239, 553, 349, 782, -958, -423, 311, -736, -212, 544, -874, -969, -166, -54, -927, -527, -859, -880, 334, 741, 365, -776, 74, 904, -464, 96, -200, 595, 798, -740, 967, 426, 561, 574, -603, 658, 4, -568, 565, 492, 444, 71, -589, -219, 298, -298, -973, 66, 989, 988, 989, -561, 12, -977, 488, 138, -144, -900, -797, 899, 96, -857, 19, 479, -696, -741, 246, 295, -332, -84, -889, 315, -971, -932, 303, -238, -904, 385, -254, 227, -336, 999, -159, -728, -860, 615, -216, -734, -304, -346, 572, -94, -624, -179, -341, -746, 414, -471, -741, 365, -368, -747, 120, 21, 22, 847, -967, 499, 638, -459, 929, 416, 262, 668, 317, 820, -927, -851, 399, -845, -14, -780, -202, -814, -549, 255, 69, -435, -254, -463, 908, -758, -290, 21, 741, -525, -892, 191, -160, 485, 348, -43, -776, 670, -66, -310, 618, -7, 386, -761, 125, 322, 318, 724, 324, 929, 359, -377, 972, -256, -976, 431, 373, -725, -204, 977, 411, -84, 767, -413, 492, -575, -824, 756, -844, 242, 624, -861, -192, -331, 767, -32, 484, -571, -685, -838, -320, 643, 838, -29, -561, 236, -757, 597, 555, 667, 893, 818, -99, 107, -113, -587, -477, 263, 193, 247, 79, 177, 992, -820, 900, 237, -914, -638, -698, -357, 267, -662, 146, 824, -947, -729, -715, 486, 138, -661, 405, 942, 714, -594, 476, 757, 980, -242, -792, -195, -407, -613, 782, 963, -981, 611, -286, -147, -819, 524, -162, 873, -203, -562, -381, 997, 731, -937, -552, 160, -480, -691, -219, 513, 995, 754, 228, 397, -998, 229, -221, -738, 346, 641, 372, 421, 140, -970, -672, 532, 914, 142, 259, -296, -883, 727, -372, -976, -825, 86, 257, -798, 52, 196, -109, 582, -218, 59, -829, 79, -218, 747, -666, -813, 671, 333, 388, -56, -205, 250, -200, 81, -629, -957, 10, 592, -17, -800, -395, -596, 413, -340, 617, -658, 493, -806, -565, 12, 637, 155, 754, 525, 187, 235, -736, 328, 457, 660, 765, 497, -55, 759, -5, 259, 580, 924, 26, -402, -50, 610, 82, -167, -4, -964, 535, 965, -571, 936, -663, -753, 714, -5, 449, -587, -541, 146, 260, -165, 267, 356, -365, -922, -881, 420, 322, 971, 931, 920, 55, 672, -13, 637, 232, 805, -583, 595, 170, -146, -602, -97, -93, -321, -885, 937, -634, -150, 608, -118, -902, -142, 927, -238, -164, -279, 597, 986, 159, 403, 858, 549, -41, 343, 23, 717, 793, 760, 612, 418, -811, -834, 543, 65, -235, 688, -897, -622, -743, -67, -319, 595, 193, 899, -785, 715, -647, 160, 652, 579, 240, 690, -971, -377, -294, 425, -285, -786, -238, -761, 747, -649, 489, -885, -551, -656, -835, 627, -767, -191, -620, -759, 700, -597, 279, 78, 561, 987, 61, 231, -105, -927, 277, -868, 483, 488, 293, 43, 559, -992, -769, 770, 769, 738, -797, -867, 955, 608, 763, 58, 335, -659, -461, 763, -758, -688, 863, -76, 653, 76, 427, 603, 231, -724, 907, 502, 751, -559, -98, -946, 639, -259, -251, 888, -244, 61, 383, 73, -215, 369, -700, -879, -244, -867, 659, 349, 194, 310, -732, 794, 355, -535, -643, 161, 179, -56, -286, -360, -426, -24, 334, 171, -541, 978, -247, 407, 909, 618, -623, 618, -859, -936, 365, 414, 320, 469, 451, -561, -107, -727, -119, -745, -167, -421, 474, 642, 28, 496, -763, -546, -138, 167, 521, -796, 196, -11, -143, -186, -500, -312, 482, -550, 77, 796, 998, 611, -196, 191, -479, -393, -367, 301, -381, 699, -458, -787, -635, -928, -87, 581, 865, 234, 276, 138, 359, -687, -238, -349, -689, 286, 41, 43, 383, 680, -688, 893, 450, 346, 492, 400, 187, 467, -392, 891, 681, -435, 985, 88, 162, 921, 984, 333, -429, 583, -104, -434, 415, 785, 367, 234, 908, -740, 948, -509, -504, 701, -557, -564, 698, 463, 820, -246, -390, 400, -815, 870, -517, 575, -940, 290, -875, 332, 315, -308, -562, 343, -344, -549, -63, -343, 816, 254, 63, 523, 922, -256, 457, 950, 17, 247, 221, -563, 172, 123, 511, -452, -750, -91, -217, -795, -679, 463, -198, 526, -977, -533, 582, 59, 107, -403, -752, 968, 31, -351, 757, 746, 170, -93, 809, 295, 318, -951, 938, -681, -725, 468, -387, -820, 905, -153, 568, -252, -696, 761, -854, -113, 271, 547, -766, -860, -390, 749, -39, -778, -846, -783, 837, 751, -166, -591, -149, -922, -126, -974, -784, -774, -166, 210, -273, -811, 923, -7, 721, -229, -964, -29, 650, 39, -939, 765, -175, -231, 203, 476, -832, 459, 979, 955, -754, -241, -657, -99, -563, 857, -777, -768, -10, -33, 518, -801, 542, 513, 254, 69, 582, 711, -361, 990, 348, 875, -280, 237, -226, 552, 630, 76, 908, -497, 683, -745, -555, -418, -561, -676, -397, -238, 767, 565, -996, -225, -850, 494, 652, 60, 874, 366, 638, -561, -645, 718, 240, 501, 591, 387, -633, 125, 550, 727, 161, -129, 813, 976, -284, 85, -578, -937, 156, 502, -10, -1, -140, -594, -711, 960, 567, 72, -822, -373, 145, 131, 410, 137, -972, 301, -1000, 829, -762, 915, 270, -81, 173, -829, 359 });

            Console.WriteLine(result);
            Console.ReadLine();
        }
    }
}
